package com.srunpass.algorithm;

/**
 * @author srunpass
 * @version Id: 矩阵中的最长递增路径, v 0.1 2024/7/3 09:59 srunpass Exp $
 */
public class 矩阵中的最长递增路径 {

    int[][] matrix;
    Integer[][] res;
    int m;
    int n;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        this.res = new Integer[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(gene(i, j), max);
            }
        }
        return max;
    }

    int gene(int i, int j) {
        if (res[i][j] != null) {
            return res[i][j];
        }
        res[i][j] = 0;
        if (i > 0 && matrix[i - 1][j] < matrix[i][j]) {
            res[i][j] = Math.max(res[i][j], gene(i - 1, j));
        }
        if (i < m - 1 && matrix[i + 1][j] < matrix[i][j]) {
            res[i][j] = Math.max(res[i][j], gene(i + 1, j));
        }
        if (j > 0 && matrix[i][j - 1] < matrix[i][j]) {
            res[i][j] = Math.max(res[i][j], gene(i, j - 1));
        }
        if (j < n - 1 && matrix[i][j + 1] < matrix[i][j]) {
            res[i][j] = Math.max(res[i][j], gene(i, j + 1));
        }
        res[i][j] = res[i][j] + 1;
        return res[i][j];
    }


}
